0240. 搜索二维矩阵 II【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - Z 字形搜索

1. 📝 题目描述

• leetcode

编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

---

示例 1：

输入：matrix = [
  [1,4,7,11,15],
  [2,5,8,12,19],
  [3,6,9,16,22],
  [10,13,14,17,24],
  [18,21,23,26,30]
], target = 5
输出：true

示例 2：

输入：matrix = [
  [1,4,7,11,15],
  [2,5,8,12,19],
  [3,6,9,16,22],
  [10,13,14,17,24],
  [18,21,23,26,30]
], target = 20
输出：false

---

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -10^9 <= matrix[i][j] <= 10^9
• 每行的所有元素从左到右升序排列
• 每列的所有元素从上到下升序排列
• -10^9 <= target <= 10^9

2. 🎯 s.1 - Z 字形搜索

c

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target) {
    int row = 0, col = matrixColSize[0] - 1;
    while (row < matrixSize && col >= 0) {
        if (matrix[row][col] == target) return true;
        else if (matrix[row][col] > target) col--;
        else row++;
    }
    return false;
}

js

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
  let row = 0,
    col = matrix[0].length - 1
  while (row < matrix.length && col >= 0) {
    if (matrix[row][col] === target) return true
    else if (matrix[row][col] > target) col--
    else row++
  }
  return false
}

py

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        row, col = 0, len(matrix[0]) - 1
        while row < len(matrix) and col >= 0:
            if matrix[row][col] == target:
                return True
            elif matrix[row][col] > target:
                col -= 1
            else:
                row += 1
        return False

• 时间复杂度：$O(m+n)$，其中 $m$ 和 $n$ 是矩阵的行数和列数
• 空间复杂度：$O(1)$

算法思路：

• 从矩阵右上角出发，每次比较当前元素与 target
• 当前元素大于 target 则左移，小于 target 则下移